#递归
class Solution:
    def numberOfWays(self, n: int, x: int) -> int:
        MOD = 10 ** 9 + 7
        # 找到第一个大于n的位置，如4^2=16大于10
        upper = bisect_left(range(n), True, key=lambda y: y**x > n)

        @cache
        def dfs(i,c):
            if i == 0:
                return 1 if c == 0 else 0
            
            res = dfs(i - 1, c)
            if c >= i ** x:
                res += dfs(i - 1, c - i ** x)
            return res % MOD
        
        return dfs(upper, n)
# 动态规划
class Solution:
    def numberOfWays(self, n: int, x: int) -> int:
        f = [1] + [0] * n
        for i in range(1,n + 1):
            v = i ** x
            if v > n:
                break
            for s in range(n, v - 1, -1):
                f[s] += f[s - v]
        return f[n] % (10 ** 9 + 7)